The construction of edge maps has heretofore been popular in automatic image processing and recognition for several reasons. Most important is the ability of edges to convey significant scene information in condensed form. This is evident by the ability of humans to interpret the edge maps of most scenes almost as readily as the line drawings they resemble.
Another advantage of edge maps is that edge lines can be mapped into other lines under affine transformations which model the effects of perspective. Therefore, edge structure is preserved from map to map when an object is seen from somewhat different aspects.
One class of methods for extracting an edge map from an image is discussed in Werner Frei and Chung-Chin-Chen, "Fast Boundary Detection; A Generalization And A New Algorithm", IEEE Transactions on Computers, Vol. C-26, Number 10, October, 1977.
Scene matching based on edge maps have superseded techniques based on cross correlation. Generally, a cross correlation technique compares a feature in a conventional intensity modulated image to a prototype in order to accept or reject the image as similar to the prototype. The advantages of an edge-based approach in cross correlation techniques are described in the following papers: S. Dudani & Carol Clark, "Vertex-Based Model Matching", Proceedings of the Symposium on Current Mathematical Problems in Image science, Monterey, Calif., Nov. 10-12, 1976; S. Dudani, J. Jenney, and B. Bullock, Correlation and Alternatives for Scene Matching: Proceedings of the 1976 IEEE Conference on Decision and Control, Clearwater, Fla., Dec. 1-3, 1976; and S. Dudani & Anthony L. Luk, "Locating Straight-Line Edge Segments on Outdoor Scenes", Proceedings of the 1977 IEEE Computer Society Conference on Pattern Recognition and Image Processing, Troy, N.Y., June 6-8, 1977.
One main disadvantage of such autocorrelation techniques is the requirement of storage of large amounts of information for each prototype against which the image is to be compared. This in turn requires large system overhead and is a relatively slow comparison process.
The present invention solves these problems by computing an edge spectrum from the edge map. The edge spectrum contains useful information in a form even more condensed than the edge map from which it is derived. The information may be processed by any of several feature detectors to determine whether, for instance, the edge map contains mutually orthogonal edges or other structural details useful in identifying the image.
The present technique of image recognition is faster than conventional methods by several orders of magnitude. Because it uses edge direction and not edge magnitude (the darkness or prominence of an edge) it is immune to changes in scene illumination and contrast. The method is amenable to pipe-lining for real time implementation, and storage problems do not normally arise because the edge spectrum is used immediately upon its computation.